/**
 * [46] 全排列
 *
 * @format
 * @lc app=leetcode.cn id=46 lang=javascript
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
// 递归+备忘录
const memo = {}
var permute = function (nums) {
    // console.log("nums:", nums)
    const N = nums.length
    if (N == 1) return [[nums[0]]]
    const res = []
    let [temp, num] = [null, 0]
    for (let i = 0; i < N; i++) {
        // console.log(i)
        num = nums[i]
        temp = []
        for (let j = 0; j < N; j++) {
            if (j == i) continue
            else temp.push(nums[j])
        }
        // console.log("temp:", temp)
        let key = temp.toString()
        // console.log("key:", key)
        if (memo[key] != undefined) temp = memo[key].map(seq => [num, ...seq])
        else {
            memo[key] = permute(temp)
            temp = memo[key].map(seq => [num, ...seq])
        }
        // console.log("temp:", temp)
        res.push(...temp)
        // console.log("res:", res)
        // console.log("memo:", memo)
    }
    return res
}
// debugger
// const nums = [1, 2, 3]
// permute(nums)
// @lc code=end
